| contributor | Institut für Architektur von Anwendungssystemen (IAAS) |
| creator | Lu, Wei |
| date | 2008-09-02 |
| description | 95 pages |
| Business process specifications can be transformed into attributed directed acyclic graphs. Querying structural information of business process specifications means that find business processes that match the query pattern and its query predicates. In this thesis, we reduce the problem of answering queries against business process specifications to the graph matching problem and present an approach to find exact or approximate answers to such queries. We defined two matching semantics, i.e. exact match and inexact match. We first present a family of stack-based structure join algorithms for an efficient query processing under the exact matching semantic. The worst case time complexity is quadratic in the average size of the query variable bindings. Then we present a new inexact graph matching algorithm to answer approximate queries on process structures by using a new similarity metric called connected component based metric and a new data structure called solution stream. The time complexity of the inexact matching algorithm is polynomial in both the size of the query graph and the size of the process graph in worst case. The algorithms presented in this thesis have been developed for querying business processes in general, as long as the corresponding graph mapping is defined. To evaluate our algorithms we apply them to query BPEL processes by taking into account BPEL-specific characteristics. | |
| format | application/pdf |
| 1524473 Bytes |
| identifier | http://www.informatik.uni-stuttgart.de/cgi-bin/NCSTRL/NCSTRL_view.pl?id=DIP-2781&engl=1 |
| language | eng |
| publisher | Stuttgart, Germany, Universität Stuttgart |
| relation | Diploma Thesis No. 2781 |
| source | ftp://ftp.informatik.uni-stuttgart.de/pub/library/medoc.ustuttgart_fi/DIP-2781/DIP-2781.pdf |
| subject | Data Structures (CR E.1) |
| Nonnumerical Algorithms and Problems (CR F.2.2) | |
| Discrete Mathematics Graph Theory (CR G.2.2) | |
| Information Search and Retrieval (CR H.3.3) | |
| Office Automation (CR H.4.1) | |
| Business Process | |
| BPEL | |
| Suchen | |
| Search | |
| Query | |
| Graph Pattern Matching | |
| title | A Graph-based Approach for Querying Structural Information of Business Processes |
| type | Text |
| Diploma Thesis |